package com.xiyou.week03.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * 78. 子集
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 * @ClassName：Subsets
 * @Author：西柚
 * @Date：2022/1/11 9:58 上午
 * @Versiion：1.0
 */
public class Subsets {

    private int n;
    private List<Integer> chosen = new ArrayList<Integer>();
    private List<List<Integer>> ans = new ArrayList<List<Integer>>();

    /**
     * 输入：nums = [1,2,3]
     * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        n = nums.length;
//        recur(nums, 0);
        recur2(nums, 0);
        return ans;
    }


    private void recur(int[] nums, int i) {
        // 递归边界
        if (i >= n) {
            // 深拷贝
            ans.add(new ArrayList<Integer>(chosen));
            return;
        }

        // 每层的相似逻辑：nums[i]选或者不选
        recur(nums, i + 1);
        chosen.add(nums[i]);
        recur(nums, i + 1);
        chosen.remove(chosen.size() - 1);
    }

    //start表示这次遍历从哪里开始
    public void recur2(int[] nums, int start){
        //树之中的每个节点都要保存，所以我们一上来就直接添加到结果。
        ans.add(new ArrayList<Integer>(chosen));
        //从上一层的节点之后（start）开始遍历到结尾
        for (int i = start; i < nums.length; i++){
            //添加到当前路径
            chosen.add(nums[i]);
            //从下一个节点开始，递归下一层
            recur2(nums, i + 1);
            //回溯
            chosen.remove(chosen.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};

        Subsets subsets = new Subsets();
        System.out.println(subsets.subsets(nums));
    }
}
